package org.leetcode.middle.leetcode45;

public class Solution {

    public int jump3(int[] nums) {
        int n = nums.length;
        if (n==1){
            return 0;
        }
        int count =0;
        int currCanJump = nums[0];
        int nextCanJump = 0;

        for (int i = 0; i < n; i++) {
            nextCanJump=Math.max(nextCanJump,i+nums[i]);

            if (currCanJump>=n-1){
                 count++;
                return count;
            }

            if (i==currCanJump ){
                currCanJump=nextCanJump;
                count++;
            }

        }


        return count;
    }

    public int jump2(int[] nums){

        if (nums.length==0 || nums.length==1 || nums==null){
            return 0;
        }

        //最大的跳转范围
        int maxDistance = 0;
        //当前的最大跳转范围
        int curMaxDistance = 0;

        int count = 0;

        for (int i = 0; i < nums.length; i++) {

            maxDistance=Math.max(maxDistance,i+nums[i]);

            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //当前移动到的下标是这次的最大跳转范围,达到了上一跳能到达的最远距离
            if (i==curMaxDistance){
                curMaxDistance=maxDistance;
                count++;
            }
        }
        return count;
    }
    public int jump(int[] nums) {

        int maxDistance=0;
        int curDistance = 0;

        int count = 0;

        for (int i = 0; i < nums.length-1; i++) {
            maxDistance=Math.max(maxDistance,i+nums[i]);

            if (maxDistance>=nums.length-1)
            {
                count++;
                break;
            }

            if (i==curDistance)
            {
                curDistance=maxDistance;
                count++;
            }
        }

        return count;
    }
}
